class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def twoSumBSTs(self, root1, root2, target):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :type target: int
        :rtype: bool
        """
        left_stack = [root1]
        right_stack = [root2]
        while left_stack[-1].left:
            node = left_stack[-1].left
            left_stack.append(node)
        while right_stack[-1].right:
            node = right_stack[-1].right
            right_stack.append(node)
        while left_stack and right_stack:
            left_node = left_stack[-1]
            right_node = right_stack[-1]
            if left_node.val + right_node.val == target:
                return True
            if left_node.val + right_node.val < target:
                left_stack.pop()
                if left_node.right:
                    next_node = left_node.right
                    left_stack.append(next_node)
                    while next_node.left:
                        next_node = next_node.left
                        left_stack.append(next_node)
            else:
                right_stack.pop()
                if right_node.left:
                    next_node = right_node.left
                    right_stack.append(next_node)
                    while next_node.right:
                        next_node = next_node.right
                        right_stack.append(next_node)
        return False

